import java.lang.reflect.Array;
import java.util.Arrays;

public class KMP {


//    28. 找出字符串中第一个匹配项的下标
//    KMP解法
    public static void main(String[] args) {
        String str = "ABCABCAABCABCD";
        String patten = "ABCABCD";
        int[] next = new int[patten.length()];
        next = getNext(patten.toCharArray(),next);
        int ret = search(str.toCharArray(),patten.toCharArray(),next);
        System.out.println(ret);//7
    }



    public static int search(char[] str, char[] patten, int[] next){
        int i = 0;
        int j = 0;
        while (i < str.length && j < patten.length) {
            if (j == -1 || str[i] == patten[j]) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }

        if (j == patten.length) {
            return i - j;
        }else {
            return -1;
        }
    }





    //    测试getNext方法
    public static void main1(String[] args) {
        String str = "ABCABCD";
        int[] next = new int[str.length()];
        next = getNext(str.toCharArray(), next);
        System.out.println(Arrays.toString(next));
//        [-1, 0, 0, 0, 1, 2, 3]
    }

//    求出next    next是prefix向右移一个下标位置组成的
//    prefix：每一个下标对应一个PMT值 组成的数组  就是该数据组成的前缀中 和 后缀中 最长交集元素长度

    public static int[] getNext(char[] patten, int[] next){
        next[0] = -1;
        int i = 0;//表示固定的patten
        int j = -1;//表示滑动的patten  第一次比较是错开比较 将第二个patten先向右移一格

        while (i < patten.length) {
            if (j == -1) {
                i++;
                j++;
            }else if (patten[i] != patten[j]) {
//                i++;  这里不需要在++  因为再循环在if(j==-1)    i会++
                j = next[j];
            }else {//       patten[i] == patten[j]
                i++;
                j++;
                next[i] = j;
            }
        }
        return next;
    }
}
